package offerbook;

/**
 * Created at 2019/11/1 0001 下午 5:03
 * 在一个递增的数组中，给定一个和sum,求两个数，是的这两个数的和是sum，找出任意一对即可。
 * 或者说输出乘积最小的那组，也指的是最外层的那对
 * 方式1：双重遍历，O(n²),没有用到排序特性.
 * 方式2：利用数组递增特性，见下面解析。
 *
 * 拓展：见{@link Code41_FindSumInArray1}
 */
public class Code41_FindSumInArray {

    /**
     * 方式2:利用有序的特点。设定两个指针。p1=0,p2 = arr.length -1。p1只增，pa只减
     * 如果arr[p1]+ arr[p2] < sum，
     * 说明arr[p1]小了，p1++,p2不变,当然任意 p2 = j < p2,会更小
     *
     * 如果arr[p1]+ arr[p2] > sum，
     * 说明arr[p2]大了，p2--,p1不变，当然任意 p1 = i > p1,会更大。
     *
     * 时间O(n),空间O(1)
     */
    public static void findSum2(int[] arr,int sum) {
        if (arr == null || arr.length == 0 || sum <= arr[0]) {
            System.out.println("找不到");
            return;
        }
        int p1 = 0;
        int p2 = arr.length -1;
        while (p1 < p2){
            //p2不可能和任何 >= p1的配对
            if(arr[p1] + arr[p2] > sum){
                p2 --;
            //p1不可能和任何 <= p2的配对
            }else if(arr[p1] + arr[p2] < sum){
                p1 ++;
            }else {
                //找到了
                System.out.println("(i,j)->("+arr[p1]+","+arr[p2]+")");
                p1 ++;
                p2 --;
            }
        }
    }
    /**
     * 方式1:
     */
    public static void findSum1(int[] arr,int sum){
        if(arr == null || arr.length == 0 || sum <= arr[0]){
            System.out.println("找不到");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length ; j++) {
                if(arr[i] + arr[j] == sum){
                    System.out.println("(i,j)->("+arr[i]+","+arr[j]+")");
                }
            }
        }
    }

    public static void main(String[] args) {
        int []arr = {2,3,4,7,8,9,12,14};
        findSum1(arr,11);
        findSum2(arr,11);
    }

}
